'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-17 10:48:36
LastEditTime: 2025-09-17 11:26:41
'''


class Solution:

    # 动态规划
    # def change(self, amount, coins):
    #     # 每个硬币都试一次
    #     n = len(coins)
    #     dp = [[0] * (amount + 1) for _ in range(n + 1)]

    #     dp[0][0] = 1

    #     for i, x in enumerate(coins):
    #         for c in range(amount + 1):
    #             if c < x:
    #                 dp[i+1][c] = dp[i][c]
    #             else:
    #                 dp[i+1][c] = dp[i][c] + dp[i+1][c - x]


    #     return dp[n][amount]
    
    # 递归搜索
    def change(self, amount, coins):
        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c == 0 else 0
            
            if c < coins[i]:
                return dfs(i - 1, c)
            
            return dfs(i - 1, c) + dfs(i, c -coins[i])
        

        return dfs(len(coins) - 1, amount)


